#include <iostream>

void insert_sort()
{
    int a[] = {5,2,4,6,3,1};

    //第一层循环做趟数
    for (int i=1; i<6; i++) {
        //方法一

        //第二层循环用来找插入位置
/*        for (int j=0; j<i; j++) {
            if(a[i] < a[j]) {
                //找到了插入位置下标为j
                //将a[j]~a[i]做循环后移一位
                int tmp = a[i];
                for(int k=i; k>=j; k--) {
                    a[k] = a[k-1];
                }
                a[j] = tmp;
            }
        }*/

        //方法二
        int tmp = a[i]; int j = i; //记录待插入元素原来的值和下标，a[0]~a[i-1]已经是有序状态
        // 从a[j-1]开始往前比较，只要比a[j]大，就后移一位，再往前一位继续比较，再大再后移一位
        while(j>0 && tmp < a[j-1]) {
            a[j] = a[j-1];
            j--;
        }
        // 退出循环说明找到了插入位置为为j，插入即可
        a[j] = tmp;
    }

    for(int i=0; i<6; i++) printf("%d ",a[i]);
}

int main() {
    std::cout << "Hello, World!" << std::endl;
    insert_sort();
    return 0;
}